package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.*;
import java.util.PriorityQueue;

public class LeetCodeMain120 {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        int sum=-1;
        while (left<=right){
            int mid=(left+right)/2;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
    public int searchInsert1(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        int sum=Integer.MAX_VALUE;
        while (left<=right){
            int mid=(left+right)/2;
            sum=mid;
            if (nums[mid]>target){
                right=mid-1;
            }else if (nums[mid]<target){
                left=mid+1;
            }else {
                return mid;
            }
        }
        if (sum==right){
            return nums.length;
        }
        if (sum==0){
            return 0;
        }
        for (int i = nums.length-1; i >= 0; i--) {
            if (nums[i]<target){
                return i;
            }
        }
        return 0;
    }
    TreeNode node=null;
    public TreeNode increasingBST(TreeNode root) {
        if (root==null){
            return null;
        }
        TreeNode n=new TreeNode(-1);
        node=n;
        inOrder(root);
        return n.right;
    }
    public void inOrder(TreeNode root){
        if (root==null){
            return;
        }
        inOrder(root.left);
        node.right=root;
        node.left=null;
        node=node.right;
        node.left=null;

        inOrder(root.right);
    }
    List<TreeNode> res=new ArrayList<>();
    public TreeNode increasingBST1(TreeNode root) {
        if (root==null){
            return null;
        }
        inOrder1(root);
        for (int i = 0; i < res.size()-1; i++) {
            res.get(i).right=res.get(i+1);
            res.get(i).left=null;
        }
        res.get(res.size()-1).left=null;
        res.get(res.size()-1).right=null;
        return res.get(0);
    }
    public void inOrder1(TreeNode root){
        if (root==null){
            return;
        }
        inOrder1(root.left);
        res.add(root);
        inOrder1(root.right);
    }
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int n:arr1) {
            map.put(n,map.getOrDefault(n,0)+1);
        }
        int length=arr1.length;
        int[] arr=new int[length];
        int count=0;
        for (int num:arr2) {
            int arr1Count=map.getOrDefault(num,0);
            if (arr1Count==0){
                continue;
            }
            for (int i = 0; i < arr1Count; i++) {
                arr[count++]=num;
            }
            map.remove(num);
        }
        if (map.isEmpty()){
            return arr;
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for (Map.Entry<Integer,Integer> set:map.entrySet()) {
            int value=set.getValue();
            for (int i = 0; i < value; i++) {
                queue.offer(set.getKey());
            }
        }
        while (!queue.isEmpty()){
            arr[count++]=queue.poll();
        }
        return arr;
    }
    public boolean canPartition(int[] nums) {
        int sum=0;
        for (int n:nums) {
            sum+=n;
        }
        if (sum%2==1){
            return false;
        }
        int[] dp=new int[10000];
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum/2; j >=nums[i] ; j--) {
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[sum/2]==sum/2;
    }
    //回溯超时
    public boolean canPartition1(int[] nums) {
        if (nums==null||nums.length==1||nums.length==0){
            return false;
        }
        int sum=0;
        Arrays.sort(nums);
        for (int n:nums) {
            sum+=n;
        }
        if (sum%2==1){
            return false;
        }
        int avg=sum/2;
        boolean[] flag=new boolean[nums.length];
        return DFS(nums,0,avg,flag,0);
    }
    public boolean DFS(int[] nums,int sum,int avg,boolean[] flag,int startIndex){
        if (sum==avg){
            return true;
        }
        for (int i = startIndex; i < nums.length&&nums[i]+sum<=avg; i++) {
            if (flag[i]){
                continue;
            }
            flag[i]=true;
            sum+=nums[i];
            if (DFS(nums, sum, avg, flag,i+1)){
                return true;
            }
            sum-=nums[i];
            flag[i]=false;
        }
        return false;
    }
    public boolean validPalindrome(String s) {
        if (s.length()==1||s.length()==2){
            return true;
        }
        if (isPrime(s)){
            return true;
        }
        int left=0;
        int right=s.length()-1;
        while (left<right){
            char ch1=s.charAt(left);
            char ch2=s.charAt(right);
            if (ch1!=ch2){
                StringBuffer buffer1=new StringBuffer();
                buffer1.append(s);
                buffer1.deleteCharAt(left);
                StringBuffer buffer2=new StringBuffer();
                buffer2.append(s);
                buffer2.deleteCharAt(right);
                if (isPrime(buffer1.toString())||isPrime(buffer2.toString())){
                    return true;
                }else {
                    return false;
                }
            }
            left++;
            right--;
        }
            return false;
    }
    public boolean isPrime(String s){
        int left=0;
        int right=s.length()-1;
        while (left<right){
            char ch1=s.charAt(left);
            char ch2=s.charAt(right);
            if (ch1!=ch2){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
